<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>39. 组合总和</title>
  </head>
  <body>
    <script>
      //     给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

      // candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

      // 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

      //

      // 示例 1：

      // 输入：candidates = [2,3,6,7], target = 7
      // 输出：[[2,2,3],[7]]
      // 解释：
      // 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
      // 7 也是一个候选， 7 = 7 。
      // 仅有这两种组合。

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/combination-sum
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

      /**
       * @param {number[]} candidates
       * @param {number} target
       * @return {number[][]}
       */
      var combinationSum = function (candidates, target) {
        const res = []
        debugger
        const dfs = (start, temp, sum) => {
          // start是当前选择的起点索引 temp是当前的集合 sum是当前求和
          if (sum >= target) {
            if (sum == target) {
              res.push(temp.slice()) // temp的拷贝 加入解集
            }
            return // 结束当前递归
          }
          for (let i = start; i < candidates.length; i++) {
            // 枚举当前可选的数，从start开始
            temp.push(candidates[i]) // 选这个数
            dfs(i, temp, sum + candidates[i]) // 基于此继续选择，传i，下一次就不会选到i左边的数
            temp.pop() // 撤销选择，回到选择candidates[i]之前的状态，继续尝试选同层右边的数
          }
        }
        dfs(0, [], 0) // 最开始可选的数是从第0项开始的，传入一个空集合，sum也为0
        return res
      }
      console.log(combinationSum([2, 3, 6, 7], 7))
    </script>
  </body>
</html>
